package com.concurrentlearn;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by Lxk on 2020/2/16.
 */
public class Main {

    private static class TreeNode {

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void showSTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode first = root, last = null;
        int count = 1;
        Stack<Integer> stack = new Stack<>();
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            stack.push(curNode.val);
            if (curNode.left != null) {
                queue.offer(curNode.left);
                last = curNode.left;
            }
            if (curNode.right != null) {
                queue.offer(curNode.right);
                last = curNode.right;
            }
            if (curNode == first) {
                //当前层次已经遍历完
                if (count % 2 == 1) {
                    for (int i = 0; i < stack.size(); i++) {
                        System.out.print(stack.get(i) + " ");
                    }
                    System.out.println();
                    stack.clear();
                } else {
                    while (!stack.isEmpty()) {
                        System.out.print(stack.pop() + " ");
                    }
                    System.out.println();
                }
                count++;
                first = last;
            }
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        TreeNode root = new TreeNode(10);
        TreeNode node = new TreeNode(6);
        TreeNode node2 = new TreeNode(13);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(8);
        TreeNode node5 = new TreeNode(11);
        TreeNode node6 = new TreeNode(16);
        root.left = node;
        root.right = node2;
        node.left = node3;
        node.right = node4;
        node2.left = node5;
        node2.right = node6;
        test.showSTree(root);
    }
}
